package com.example.sort;

import java.util.Arrays;

/**
 * @author: Bin.L
 * @date: 2022/7/21  15:23
 * @description: 鸡尾酒排序(元素比较和交换是双向的), 冒泡排序升级: 适用于大部分元素有序的情况下
 */

public class CocktailSort {

    public static void main(String[] args) {
        // 鸡尾酒排序 - 适用于大部分元素有序的情况下
        int[] ints = {2, 3, 4, 5, 6, 7, 8, 9, 1};
        sort(ints);
        System.out.println(Arrays.toString(ints));
    }

    public static void sort(int[] ints) {
        int tmp = 0;
        // 奇数轮, 从左向右比较交换
        for (int i = 0; i < ints.length / 2; i++) {
            // 有序标记, 每一轮的初始值都是true
            boolean isSorted = true;
            for (int j = i; j < ints.length - i - 1; j++) {
                if (ints[j] > ints[j + 1]) {
                    tmp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = tmp;
                    // 有元素交换, 不是有序
                    isSorted = false;
                }
            }

            if (isSorted) {
                break;
            }

            isSorted = true;
            //偶数轮, 从右向左比较和交换
            for (int j = ints.length - i - 1; j > i; j--) {
                if (ints[j] < ints[j - 1]) {
                    tmp = ints[j];
                    ints[j] = ints[j - 1];
                    ints[j - 1] = tmp;
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }

}
